package cn.orange.ch07_binarytree;

import cn.orange.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * LC257.二叉树的所有路径
 */
public class LC257 {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> paths = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        findPaths(root, path, paths);
        return paths;
    }
    private void findPaths(TreeNode root, List<Integer> path, List<String> paths) {
        path.add(root.val);
        if (root.left == null && root.right == null) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < path.size() - 1; i++) {
                sb.append(path.get(i)).append("->");
            }
            sb.append(path.get(path.size() - 1));
            paths.add(sb.toString());
            return;
        }
        if (root.left != null) {
            findPaths(root.left, path, paths);
            path.remove(path.size() - 1);
        }
        if (root.right != null) {
            findPaths(root.right, path, paths);
            path.remove(path.size() - 1);
        }
    }

    public static void main(String[] args) {
        LC257 alg = new LC257();
        TreeNode root = new TreeNode(1, new TreeNode(2), new TreeNode(3));
        root.left.right = new TreeNode(5);
        System.out.println(alg.binaryTreePaths(root));
    }
}
